package Leetcode.每日一题;

import java.util.Arrays;

/**
 * @ClassName 英雄的力量
 * @since: 2023/8/2 09:08
 * @auth: kirito
 * @description:给你一个下标从 0 开始的整数数组 nums ，
 * 它表示英雄的能力值。如果我们选出一部分英雄，这组英雄的 力量 定义为：
 *
 * i0 ，i1 ，... ik 表示这组英雄在数组中的下标。那么这组英雄的力量为
 * max(nums[i0],nums[i1] ... nums[ik])2 * min(nums[i0],nums[i1] ... nums[ik]) 。
 *
 * 感觉就是求数组的子集的（平方和）
 * 可以用动态规划？每个数的的本身平方可以保留
 * 然后两个变量 max min保存本次遍历的最大和最小值
 * 思路应该对  但是求子集这卡住了。。。
 **/
public class 英雄的力量 {
    public static int sumOfPower(int[] nums) {
        Arrays.sort(nums);
        int[] dp = new int[nums.length];
        int[] preSum = new int[nums.length + 1];
        int res = 0, mod = 1000000007;
        for (int i = 0; i < nums.length; i++) {
            dp[i] = (nums[i] + preSum[i]) % mod;
            preSum[i + 1] = (preSum[i] + dp[i]) % mod;
            res = (int) ((res + (long) nums[i] * nums[i] % mod * dp[i]) % mod);
            if (res < 0) {
                res += mod;
            }
        }
        return res;
    }

    public static void main(String[] args) {
        int[] nums = {2, 1, 4};
        System.out.println(sumOfPower(nums));
    }
}
